class Solution {
    // 994. 腐烂的橘子
    public int orangesRotting(int[][] grid) {
        int rowNum = grid.length; // 行(高)
        int colNum = grid[0].length; // 列 （长）

        int minute =0;// 所需时间

        Queue<int[]> queue = new LinkedList<>();

        // 新鲜橘子数量
        int newCount = 0;

        for (int i = 0; i<rowNum;i++){
            for (int j= 0;j<colNum;j++){
                int thisGrid = grid[i][j];
                if (thisGrid==1){
                    newCount++;
                }else if (thisGrid==2){
                    ((LinkedList<int[]>) queue).add(new int[]{i,j});
                }
            }
        }

        while (newCount>0&&!queue.isEmpty()){
            minute++;

            int badNum=queue.size();

            for (int i=0;i<badNum;i++){
                // 拿出一个坏的
                int[] bad = queue.poll();
                int r = bad[0];
                int c = bad[1];
                if (r-1>=0&&grid[r-1][c]==1){
                    grid[r-1][c] = 2; // 好橘子变成坏橘子
                    newCount--; //好橘子-1
                    // 加入坏橘子
                    ((LinkedList<int[]>) queue).add(new int[]{r-1,c});
                }

                if (r+1<rowNum&&grid[r+1][c]==1){
                    grid[r+1][c] = 2; // 好橘子变成坏橘子
                    newCount--; //好橘子-1
                    // 加入坏橘子
                    ((LinkedList<int[]>) queue).add(new int[]{r+1,c});
                }
                if (c-1>=0&&grid[r][c-1]==1){
                    grid[r][c-1] = 2; // 好橘子变成坏橘子
                    newCount--; //好橘子-1
                    // 加入坏橘子
                    ((LinkedList<int[]>) queue).add(new int[]{r,c-1});

                }

                if (c+1<colNum&&grid[r][c+1]==1){
                    grid[r][c+1] = 2; // 好橘子变成坏橘子
                    newCount--; //好橘子-1
                    // 加入坏橘子
                    ((LinkedList<int[]>) queue).add(new int[]{r,c+1});
                }
            }
        }

        if (newCount>0){
            return -1;
        }else {
            return minute;
        }

    }
}